package 链表和树.链表;

import org.w3c.dom.Node;

//Java：随机链表的复制
public class CopyListWithRandomPointer{
    public static void main(String[] args) {
        Solution solution = new CopyListWithRandomPointer().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

//class Node {
//    int val;
//    Node next;
//    Node random;
//
//    public Node(int val, Node next) {
//        this.val = val;
//        this.next = null;
//        this.random = null;
//    }
//}

class Solution {
        //画图解题新老交错完确立新的random，再分离
    public Node copyRandomList(Node head) {
        if(head == null){
            return null;
        }

        //首先复制每一个节点直接将新节点插入到老节点
        for(Node cur = head; cur != null ;cur = cur.next.next){
            cur.next = new Node(cur.val,cur.next);//刚好插入在中间

        }
        //遍历交错的链表原始的节点保存random映射了
        for(Node cur =head; cur != null; cur = cur.next.next){
            if(cur.random != null){
                cur.next.random = cur.random.next;//如果只是randow就是老链表的randow刚好新的在下一个
            }
        }

        //分离老新链表
        Node newHead = head.next;
        Node cur = head;//外面定义
        for(; cur.next.next != null ; cur = cur.next){
            Node newNode = cur.next;
            cur.next = newNode.next;
            newNode.next = newNode.next.next;
        }

        cur.next = null;
        return newHead;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}